One responsibility of file systems is the management of memory. File system memory is generally composed of both virtual and physical memory. Virtual memory allows the file system to present a single contiguous memory space for all file system applications while the underlying physical memory may be fragmented or composed of various memory devices with their own physical memory spaces. The file system translates a virtual address into a physical address each time physical memory is accessed. The translation of a virtual address into a physical address is referred to as a mapping from virtual to physical memory.
Physical memory in a file system is often dispersed across many different memory devices. These memory devices can include RAM, one or more internal hard drives, and one or more external memory volumes. Physical memory is typically organized into extents, and extents are subdivided into blocks. The data contents of a file ultimately reside within one or more blocks of physical memory.
Typically, files in a traditional file system are managed by creating a record for each file and organizing all of the records within a data structure. Most file systems refer to these records as inodes. Each inode contains mapping information such as the virtual and physical memory addresses of the memory contents, the amount of memory used, and information about the data (e.g. metadata).
Data stored in an extent can be shared between files. One example of when sharing occurs is when a file snapshot is performed by the file system. The created snapshot does not result in a duplication of the original memory contents. Rather, the original file and the snapshot file share the memory contents. Memory contents can be shared among any number of files. Shared physical memory contents are accessed either through the original file or the newly created file.
Some operations in a file system require that data in physical memory be relocated. For example, during the course of creating and deleting files, physical memory may become fragmented. Traditional file systems manage memory relocation at the granularity of physical memory blocks. Fragmented memory occurs when the blocks that together hold the data contents of a single file are not grouped together in a physically contiguous memory area. A defragmentation operation moves the blocks holding the contents of a single file into contiguous memory blocks.
When memory contents are shared among multiple files, additional measures must be taken during data relocation to ensure that each file sharing the memory contents has its corresponding inode correctly updated. More particularly, the mapping information for each inode must be updated to reflect the new physical memory addresses of the blocks storing the shared memory contents. In traditional file systems, the relocation is performed inefficiently due, in part, to traditional file systems not maintaining information on the shared portions of memory any differently than the non-shared portions of memory. It is therefore desirable to create a new data structure to maintain information on the inodes that share data. This new data structure is used for efficiently performing an inode update process. Further, the inode update process can be made even more efficient by having the new data structure maintain extent-level information, instead of the traditional file system maintenance of block-level information.